package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.Stack;

/**
 * 面试题30. 包含min函数的栈
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 *
 *
 *
 * 示例:
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *
 *
 * 提示：
 *
 * 各函数的调用总次数不超过 20000 次
 */
public class LeetCode1553 {

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-1);
        System.out.println(minStack.min());
        System.out.println(minStack.top());
    }
}

class MinStack {

    private Stack<Integer> data = new Stack<>();

    private Stack<Integer> min = new Stack<>();

    private Stack<Integer> max = new Stack<>();

    /** initialize your data structure here. */
    public MinStack() {



    }

    public void push(int x) {
        data.push(x);
        if (min.isEmpty()){
            min.push(x);
        }else if (min.peek() >= x){
            min.push(x);
        }else{
            min.push(min.peek());
        }
        if (max.isEmpty()){
            max.push(x);
        }else if (max.peek() <= x){
            max.push(x);
        }else{
            max.push(max.peek());
        }
    }

    public void pop() {
        data.pop();
        min.pop();
        max.pop();
    }

    public int top() {
        return max.peek();
    }

    public int min() {
        return min.peek();
    }
}
